import java.util.*;
//left + ((rigth - left) >> 1))二分查找写法，防止溢出
/*剑指 Offer 09. 用两个栈实现队列*/
/**
class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void appendTail(int value) {
        push(value);
    }

    public int deleteHead() {
        return pop();
    }

    public void push(int x) {
        stack1.push(x);
    }
    public int pop() {
        if (empty()){
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (empty()){
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty()&& stack2.isEmpty();
    }
}
 */
public class Solution {
    /*剑指 Offer 10- I. 斐波那契数列
    *  f(0)=0,f(1)=1,f(2)=1*/
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;
    }
    /*剑指 Offer 10- II. 青蛙跳台阶问题
    *  f(0)=1 f(1)=1, f(2)=2*/
    public int numWays(int n) {
        final int MOD = 1000000007;
        int a=1,b=1,r=0;
        for (int i = 0; i < n; i++) {
            r=(a+b)%MOD;
            a=b;
            b=r;
        }
        return a;
    }
    /*剑指 Offer 11. 旋转数组的最小数字
    * 1：为什么right--不会对结果产生影响？
    *   因为只有当最小数字唯一才会对结果产生影响，而这与判定条件冲突
    * 2：为什么right==mid 而left=mid+1
    *因为当numbers[mid]>numbers[right]时，mid肯定不是最小值，而当
    * numbers[mid]<numbers[right]时，right包含了mid，最后left都是要和right相等的
    * 3:时间空间复杂度是多少
    * 时间复杂度度 O(logN)~O(N)
    * 空间复杂度  O（1）
    * */
    public int minArray(int[] numbers) {

        int left=0;
        int right=numbers.length-1;
        while (left<right){
            int mid=(left+right)/2;
            if (numbers[mid]>numbers[right]){
                left=mid+1;
            }else if(numbers[mid]==numbers[right]) {
                right--;
            }else{
                right=mid;
            }
        }
        return numbers[left];
    }
    /*剑指 Offer 05. 替换空格
    * */
    public String replaceSpace(String s) {
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)==' '){
                sb.append("%20");
            }else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
    /*剑指 Offer 06. 从尾到头打印链表
    解法：栈/递归,或者逆序插入数组，或者反转链表后在插入数组*/
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
    /*剑指 Offer 25. 合并两个排序的链表*/
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
    /*剑指 Offer 27. 二叉树的镜像*/
     class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    public TreeNode mirrorTree(TreeNode root) {
          if (root==null)return null;
          TreeNode newleft=mirrorTree(root.right);
          TreeNode newright=mirrorTree(root.left);
          root.left=newleft;
          root.right=newright;
          return root;
    }
    /*剑指 Offer 28. 对称的二叉树*/
    private boolean isSameTree(TreeNode p,TreeNode q){
        //判断一个节点为空和一个节点不为空的情况
        if (p == null && q!= null || p!=null && q== null)return false;
        //判断都是空的情况
        if (p== null && q==null)return true;
        if (p.val != q.val)return false;
        return isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);

    }
    public boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot==null)return true;
        return isSameTree(pRoot.left,pRoot.right);
    }
    /*剑指 Offer 21. 调整数组顺序使奇数位于偶数前面*/
    public int[] exchange(int[] nums) {
        //双指针
        int left=0;
        int right=nums.length-1;
        while (left<right){
            if (nums[left]%2==0){
                while (left<right&&nums[right]%2==0){
                    right--;
                }
                int tmp=nums[left];
                nums[left]=nums[right];
                nums[right]=tmp;
            }
            left++;
        }
        return nums;
    }
    /*剑指 Offer 15. 二进制中1的个数*/
    public int hammingWeight(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n = (n - 1) & n;
        }
        return sum;
    }
    /*重点：要多看几次剑指 Offer 29. 顺时针打印矩阵*/
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        //行的长度与列的长度
        int rows = matrix.length, columns = matrix[0].length;
        int[] order = new int[rows * columns];
        //下标的指向
        int index = 0;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order[index++] = matrix[top][column];
            }
            for (int row = top + 1; row <= bottom; row++) {
                order[index++] = matrix[row][right];
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order[index++] = matrix[bottom][column];
                }
                for (int row = bottom; row > top; row--) {
                    order[index++] = matrix[row][left];
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
    /*剑指 Offer 22. 链表中倒数第k个节点*/
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head;
        ListNode slow=head;

        while(k>0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    /*剑指 Offer 17.要多看，好难啊 打印从1到最大的n位数
    * 考虑大数的情况
    * 大数的表示应用字符串 String 类型*/
   /* StringBuilder res;
    int count = 0, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder(); // 数字字符串集
        num = new char[n]; // 定义长度为 n 的字符列表
        dfs(0); // 开启全排列递归
        res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号
        return res.toString(); // 转化为字符串并返回
    }
    void dfs(int x) {
        if(x == n) { // 终止条件：已固定完所有位
            res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部，使用逗号隔开
            return;
        }
        for(char i : loop) { // 遍历 ‘0‘ - ’9‘
            num[x] = i; // 固定第 x 位为 i
            dfs(x + 1); // 开启固定第 x + 1 位
        }
    }*/
    /*剑指 Offer 24. 反转链表*/
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
    /*剑指 Offer 18. 删除链表的节点*/
    public ListNode deleteNode(ListNode head, int val) {
        ListNode pre=new ListNode(-1);

        pre.next=head;
        ListNode pree=pre;
        ListNode cur=head;
        while (cur!=null){
            ListNode tmp=cur.next;
            if (cur.val==val){
                pree.next=tmp;
            }
            pree=cur;
            cur=tmp;
        }
        return pre.next;
    }

    /*剑指 Offer 40. 最小的k个数*/
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0)return new int[k];
        //优先级队列默认是小根堆
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            if (i<k){
                priorityQueue.offer(arr[i]);
            }else {
                if (arr[i]<priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.offer(arr[i]);
                }
            }
        }
        int[] ret=new int[k];
        for (int i = 0; i < k; i++) {
            ret[i]=priorityQueue.poll();
        }
        return ret;
    }
    /*重点&&：剑指 Offer 42. 连续子数组的最大和*/
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int former = 0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0
        int cur = nums[0];//用于记录dp[i]的值
        for(int num:nums){
            cur = num;
            if(former>0) cur +=former;
            if(cur>max) max = cur;
            former=cur;
        }
        return max;
    }
    /*剑指 Offer 39. 数组中出现次数超过一半的数字
    * 解法：哈希表或排序*/
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();

        for (int num:nums) {
            if (map.get(num)==null){
                map.put(num,1);
            }else {
                map.put(num,map.get(num)+1);
            }
        }
        for (int num:nums) {
            if (map.get(num)>nums.length/2){
                return num;
            }
        }
        return -1;
    }
    /*剑指 Offer 32 - II. 从上到下打印二叉树 II*/
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) {
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
    /*剑指 Offer 50. 第一个只出现一次的字符*/
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (map.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
    /*剑指 Offer 55 - I. 二叉树的深度*/
    public int maxDepth(TreeNode root) {
        if (root==null)return 0;
        int leftH=maxDepth(root.left);
        int rightH=maxDepth(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }
    /*重点&&：剑指 Offer 57. 和为s的两个数字*/
    public int[] twoSum(int[] nums, int target) {
        int j=nums.length-1;
        int[] arr=new int[2];
        for (int i=0;i<j;) {
            if (target - nums[i] == nums[j]) {//防止溢出
                arr[0] = nums[i];
                arr[1] = nums[j];
                break;
            } else if (nums[j] + nums[i] > target) {
                j--;
            } else {
                i++;
            }
        }
        return arr;
    }
    /*重点&&：剑指 Offer 57 - II. 和为s的连续正数序列  */
    public int[][] findContinuousSequence(int target) {
        int i = 1; // 滑动窗口的左边界
        int j = 1; // 滑动窗口的右边界
        int sum = 0; // 滑动窗口中数字的和
        List<int[]> res = new ArrayList<>();

        while (i <= target / 2) {
            if (sum < target) {
                // 右边界向右移动
                sum += j;
                j++;
            } else if (sum > target) {
                // 左边界向右移动
                sum -= i;
                i++;
            } else {
                // 记录结果
                int[] arr = new int[j-i];
                for (int k = i; k < j; k++) {
                    arr[k-i] = k;
                }
                res.add(arr);
                // 左边界向右移动
                sum -= i;
                i++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }
    /*剑指 Offer 52. 两个链表的第一个公共节点*/
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode l1=headA;
        ListNode l2=headB;

        while (l1!=l2){
            if (l1==null){
                l1=headB;
            }else {
                l1=l1.next;
            }
            if (l2==null){
                l2=headA;
            }else {
                l2=l2.next;
            }
        }
        return l1;
    }

    /*剑指 Offer 58 - I. 翻转单词顺序*/
    public String my_reverseWords(String s) {
        char[] ch=s.toCharArray();
        StringBuilder stringBuilder=new StringBuilder();
        Stack<String> stack=new Stack<>();


       boolean flg=false;
        for (int i = 0; i <ch.length ; i++) {
            if (ch[i] != ' '){
                stringBuilder.append(ch[i]);
                flg=true;
            }else if (flg){
                stack.push(stringBuilder.toString());
                stringBuilder=new StringBuilder();
                flg=false;
            }
        }
        if (flg){
            stack.push(stringBuilder.toString());
        }
        String str=new String();
        while (!stack.isEmpty()){
            if (stack.size()-1==0){
                str=str+stack.pop().toString();
            }else {
                str=str+stack.pop().toString()+" ";
            }
        }
        return str;
    }
    //双指针解法
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }

    /*剑指 Offer 53 - I. 在排序数组中查找数字 I
    * 二分法写*/
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
    /*剑指 Offer 53 - II. 0～n-1中缺失的数字*/
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i<=j){
            int m = (i + j) / 2;
            if (nums[m]==m){
                i=m+1;
            }else {
                j=m-1;
            }
        }
        return i;
    }
    /*剑指 Offer 54. 二叉搜索树的第k大节点
    * 没有注意到是二叉搜索树，所以直接使用了优先级队列，但我这种具有普遍性*/
    public int my_kthLargest(TreeNode root, int k) {
        if (root==null)return -1;
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;

        while (cur!=null || !stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                if (k>0){
                    priorityQueue.offer(cur.val);
                    k--;
                }else {
                    if (cur.val>priorityQueue.peek()){
                        priorityQueue.poll();
                        priorityQueue.offer(cur.val);
                    }
                }
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
        return priorityQueue.poll();
    }
    /*利用二叉搜索树的中序遍历是有序数列性质，说明逆序是降序的，以此来进行*/
    public int kthLargest(TreeNode root, int k) {
        if (root==null)return -1;
        Deque<TreeNode> stack=new LinkedList<>();
        Deque<Integer> stack2=new LinkedList<>();
        TreeNode cur=root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top=stack.pop();
            stack2.push(top.val);
            cur=top.right;
        }
        for (int i = 0; i < k-1; i++) stack2.poll();
        return stack2.isEmpty()?-1:stack2.poll();
    }
    /*剑指 Offer 65. 不用加减乘除做加法*/
    public int add(int a, int b) {

      /* 以后看到不用符号，就去考虑异或
      这是不用符号，交换俩个数的值
      a=a^b;
       b=a^b;
       a=a^b;*/
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;

    }
    /*面试题61. 扑克牌中的顺子*/
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }

    /*剑指 Offer 55 - II. 平衡二叉树
    * 第一种写法*/
    public boolean isBalanced(TreeNode root) {
        return getHeight(root)==-1?false:true;
    }
    public int getHeight(TreeNode root) {
        if (root == null){
            return 0;
        }
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);

        if (rightH>=0 && leftH>=0 && Math.abs(leftH-rightH)<=1){
            return Math.max(leftH,rightH)+1;
        }else {
            return -1;
        }
    }
    /*剑指 Offer 62. 圆圈中最后剩下的数字*/
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
    /*剑指 Offer 68 - I. 二叉搜索树的最近公共祖先*/
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return  null;
        }
        if (root == p || root == q){
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        if (left ==null && right !=null){
            return right;
        }else if (left != null && right ==null){
            return  left;
        }else if (left != null && right != null){
            return root;
        }
        return null;
    }
    /*剑指 Offer II 001. 整数除法*/
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;//将a,b得符号位提取出来
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            // 首先，右移的话，再怎么着也不会越界
            // 其次，无符号右移的目的是：将 -2147483648 看成 2147483648

            // 注意，这里不能是 (a >>> i) >= b 而应该是 (a >>> i) - b >= 0
            // 这个也是为了避免 b = -2147483648，如果 b = -2147483648
            // 那么 (a >>> i) >= b 永远为 true，但是 (a >>> i) - b >= 0 为 false
            if ((a >>> i) - b >= 0) { // a >= (b << i)
                a -= (b << i);
                // 代码优化：这里控制 res 大于等于 INT_MAX
                if (res > Integer.MAX_VALUE - (1 << i)) {
                    return Integer.MIN_VALUE;
                }
                res += (1 << i);
            }
        }
        // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
        return sign == 1 ? res : -res;
    }
    /*剑指 Offer II 003. 前 n 个数字二进制中 1 的个数*/
    public int[] countBits(int n) {
        int[] ret=new int[n+1];
        for (int i = 0; i < n+1; i++) {
            int count=0;
            int k=i;
            while (k>0){
                count++;
                k=k&(k-1);
            }
            ret[i]=count;
        }
        return ret;
    }
    /*剑指 Offer II 002. 二进制加法*/
    public String addBinary(String a, String b) {
        StringBuilder a1=new StringBuilder(a);
        StringBuilder b1=new StringBuilder(b);
        a1=a1.reverse();
        b1=b1.reverse();
        StringBuilder stringBuilder=new StringBuilder();
        int flag=0;//标识进位
        int i=0,j=0;
        while (i < a1.length() || j < b1.length()){
            if (i < a1.length() && j < b1.length()){
                int sum=a1.charAt(i)-'0'+b1.charAt(j)-'0'+flag;
                flag=sum/2;
                stringBuilder.append(sum%2);
                i++;
                j++;
            }else if (i < a1.length()){
                int sum=a1.charAt(i)-'0'+flag;
                flag=sum/2;
                stringBuilder.append(sum%2);
                i++;
            }else {
                int sum=b1.charAt(j)-'0'+flag;
                flag=sum/2;
                stringBuilder.append(sum%2);
                j++;
            }
        }
        if (flag>0){
            stringBuilder.append(flag);
        }

        stringBuilder.reverse();
        return stringBuilder.toString();
    }

    /*剑指 Offer II 006. 排序数组中两个数字之和
    * 上面那个是找数字，这个是找下标*/
    public int[] twoSum2(int[] nums, int target) {
        int j=nums.length-1;
        int[] arr=new int[2];
        for (int i=0;i<j;) {
            if (target - nums[i] == nums[j]) {//防止溢出
                arr[0] = i;
                arr[1] = j;
                break;
            } else if (nums[j] + nums[i] > target) {
                j--;
            } else {
                i++;
            }
        }
        return arr;
    }

    /*剑指 Offer II 088. 爬楼梯的最少成本*/
   /* public int minCostClimbingStairs(int[] cost) {

    }*/
    /*剑指 Offer II 012. 左右两边子数组的和相等*/
    public int pivotIndex(int[] nums) {
        int sumLeft = 0, sumRight = Arrays.stream(nums).sum();
        for (int i = 0; i < nums.length; i++) {
            sumRight -= nums[i];
            // 若左侧元素和等于右侧元素和，返回中心下标 i
            if (sumLeft == sumRight)
                return i;
            sumLeft += nums[i];
        }
        return -1;
    }
    /*剑指 Offer II 018. 有效的回文*/
    public boolean isPalindrome(String s) {

        int left=0;
        int right=s.length()-1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                //Character.isLetterOrDigit该方法确定指定的字符是否是字母或数字。
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
    /*剑指 Offer II 019. 最多删除一个字符得到回文*/
    public boolean validPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) {
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 == c2) {
                ++low;
                --high;
            } else {
                return validPalindrome(s, low, high - 1) || validPalindrome(s, low + 1, high);
            }
        }
        return true;
    }

    public boolean validPalindrome(String s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }
    /*剑指 Offer II 027. 回文链表*/
    public boolean isPalindrome(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (fast != null && fast.next !=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        slow=reverseList(slow);
        fast=head;
        while (slow!=null){
            if (fast.val == slow.val){
                fast=fast.next;
                slow=slow.next;
            }else {
                return false;
            }
        }
        return true;
    }
    /*剑指 Offer II 032. 有效的变位词*/
    public boolean my_isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch=s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch=t.charAt(i);

            if (map.get(ch) == null|| map.get(ch)<=0){
               return false;
            }else {
                map.put(ch,map.get(ch)-1);
            }
        }

        return true;
    }
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }















   














}

